//
// Created by Snow on 2023/4/1.
//
////二叉树的遍历
//【例7.18】的算法：采用层次遍历方法输出从根节点到每个叶子节点的路径逆序列
#include<cstdio>
#include <cstdlib>
#define MaxSize 50
typedef char ElemType;
typedef struct node
{
    ElemType data;//数据元素
    struct node *lchild;//指向左孩子结点
    struct node *rchild;//指向右孩子结点
}BTNode;
//创建二叉树
void CreatBTree(BTNode *&b,const char *str)
{
    BTNode *St[MaxSize],*p;//st数组作为顺序栈
    int top=-1,k,j=0;//top为栈顶指针
    char ch;
    b=nullptr;//初始时二叉链为空
    ch=str[j];
    while(ch!='\0')//遍历str中的每一个字符
    {
        switch(ch)
        {
            case '(':top++;St[top]=p;k=1;break;//开始处理左孩子结点
            case ')':top--;break;//栈顶结点的子树处理完毕
            case ',':k=2;break;//开始处理右孩子结点
            default:
                p=(BTNode*)malloc(sizeof(BTNode));//创建一个结点，有p指向他
                p->data=ch;//存放结点值
                p->lchild=p->rchild=nullptr;//左、右指针都设置为空
                if(b==nullptr)//若尚未建立根结点
                    b=p;//p所指向的结点作为根节点
                else//已建立二叉树根节点
                {
                    switch(k)
                    {
                        case 1:St[top]->lchild=p;break;//新建结点作为栈顶结点的左孩子
                        case 2:St[top]->rchild=p;break;//新建结点作为栈顶结点的右孩子
                    }
                }
        }
        j++;
        ch=str[j];//继续遍历str
    }
}
//销毁二叉树
void DestroyBTree(BTNode *&b)
{
    if(b!=nullptr)
    {
        DestroyBTree(b->lchild);
        DestroyBTree(b->rchild);
        free(b);
    }
}
//输出二叉树
void DispBTree(BTNode *b)
{
    if(b!=nullptr)
    {
        printf("%c",b->data);
        if(b->lchild!=nullptr||b->rchild!=nullptr)
        {
            printf("(");//有孩子结点时才输出"("
            DispBTree(b->lchild);//递归输出左子树
            if(b->rchild!=nullptr)
                printf(",");//有右孩子才输出","
            DispBTree(b->rchild);//递归输出右子树
            printf(")");//有孩子结点时才输出")"
        }
    }
}

//----------------------------------------------------------
//-非环形队列的基本运算算法---------------------------------
//----------------------------------------------------------
typedef struct SNode
{
    BTNode *pt;						//存放当前节点指针
    int parent;						//存放双亲节点在队列中的位置
} NodeType;							//非环形队列元素类型

typedef struct
{
    NodeType data[MaxSize];			//存放队列元素
    int front,rear;					//队头指针和队尾指针
} QuType;							//顺序队类型


void InitQueue(QuType *&q)			//初始化队列
{	q=(QuType *)malloc (sizeof(QuType));
    q->front=q->rear=-1;
}
void DestroyQueue(QuType *&q)		//销毁队列
{
    free(q);
}
bool QueueEmpty(QuType *q)			//判断队列是否为空
{
    return(q->front==q->rear);
}
bool enQueue(QuType *&q,NodeType e)	//进队列
{	if (q->rear==MaxSize-1)			//队满上溢出
        return false;				//返回假
    q->rear++;						//队尾增1
    q->data[q->rear]=e;				//rear位置插入元素e
    return true;					//返回真
}
bool deQueue(QuType *&q,NodeType &e) //出队列
{	if (q->front==q->rear)			//队空下溢出
        return false;
    q->front++;
    e=q->data[q->front];
    return true;
}
//----------------------------------------------------------
void AllPath2(BTNode *b)
{
    int k;
    BTNode *p;
    NodeType qelem;
    QuType *qu;							//定义非非环形队列指针
    InitQueue(qu);						//初始化队列
    qelem.pt=b; qelem.parent=-1;		//创建根节点对应的队列元素
    enQueue(qu,qelem);					//根节点进队
    while (!QueueEmpty(qu))				//队不空循环
    {
        deQueue(qu,qelem);				//出队元素qelem,它在队中下标为qu->front
        p=qelem.pt;						//取元素qelem的节点p
        if (p->lchild==nullptr && p->rchild==nullptr)	//节点p为叶子节点
        {
            k=qu->front;				//输出节点p到根节点的路径逆序列
            while (qu->data[k].parent!=-1)
            {
                printf("%c->",qu->data[k].pt->data);
                k=qu->data[k].parent;
            }
            printf("%c\n",qu->data[k].pt->data);
        }
        if (p->lchild!=nullptr)			//节点p有左孩子
        {
            qelem.pt=p->lchild;			//创建节点p的左孩子对应的队列元素
            qelem.parent=qu->front;		//节点p的左孩子的双亲位置为qu->front
            enQueue(qu,qelem);			//节点p的左孩子进队
        }
        if (p->rchild!=nullptr)			//节点p有右孩子
        {
            qelem.pt=p->rchild;			//创建节点p的右孩子对应的队列元素
            qelem.parent=qu->front;		//节点p的右孩子的双亲位置为qu->front
            enQueue(qu,qelem);			//节点p的右孩子进队
        }
    }
    DestroyQueue(qu);
}

int main()
{
    BTNode *b;
    CreatBTree(b,"A(B(D(,G)),C(E,F))");
    printf("b:");
    DispBTree(b);
    printf("\n");
    AllPath2(b);
    DestroyBTree(b);
    return 1;
}